#include <iostream>
using namespace std;

// 找到基准元素
int part(int A[], int low, int high)
{
  // 首位置为基准元素
  int pivot = A[low];
  
  // 将基准元素插入对应位置
  while (low < high)
  {
    // 从右往左，找到第一个小于基准的元素
    while (low < high && A[high] >= pivot)
      --high;
    
    // 交换
    A[low] = A[high];
    
    // 从左往右，找到第一个大于基准的元素
    while (low < high && A[low] <= pivot)
      ++low;
    
    // 交换
    A[high] = A[low];
  }
  
  // 将基准插入对应位置
  A[low] = pivot;
  
  // 返回位置序号
  return low;
}

// 快速排序
void Quicksort(int A[], int low, int high)
{
  if (low < high)
  {
    // 找到基准元素
    int pivotpos = part(A, low, high);
    
    // 对左半部分进行快速排序
    Quicksort(A, low, pivotpos - 1);
    
    // 对右半部分进行快速排序
    Quicksort(A, pivotpos + 1, high);
  }
}


int main()
{
  // 创建数组
  int A[] = {12, 6, 9, 2, 4};
  
  // 快速排序
  Quicksort(A, 0, 4);
  
  // 打印
  for (int i = 0; i < 5; i++)
  {
    cout << A[i] << ' ';
  }
  return 0;
}